from random import *

def partition(a, start, end, pivotIndex):
    low = start
    high = end - 1  # After we remove pivot it will be one smaller
    pivotValue = a[pivotIndex].vlsort
    temp=a[pivotIndex]
    a[pivotIndex] = a[end]
    while True:
        while low <= high and a[low].vlsort < pivotValue:
            low = low + 1
        while low <= high and a[high].vlsort >= pivotValue:
            high = high - 1
        if low > high:
            break
        a[low], a[high] = a[high], a[low]
    a[end] = a[low]
    a[low] = temp
    return low

def insertionSort(a, start, end):
    for i in xrange(start, end + 1):
        # Insert a[i] into the sorted sublist
        v = a[i]
        for j in reversed(xrange(0, i)):
            if a[j].vlsort <= v.vlsort:
                a[j + 1] = v
                break
            a[j + 1] = a[j]
        else:
            a[0] = v
    return a


def qsortRange(a, start, end):
    if end - start + 1 < 32:
        insertionSort(a, start, end)
    else:
        pivotIndex = partition(a, start, end, randint(start, end))
        qsortRange(a, start, pivotIndex - 1)
        qsortRange(a, pivotIndex + 1, end)
    return a
